package com.zjsru.plan2023.other;

/**
 * @Author: cookLee
 * @Date: 2023-09-25
 * 数组中的最长山脉
 */
public class LongestMountain {

    /**
     * 输入：arr = [2,1,4,7,3,2,5]
     * 输出：5
     * 解释：最长的山脉子数组是 [1,4,7,3,2]，长度为 5。
     * \
     * 输入：arr = [2,2,2]
     * 输出：0
     * 解释：不存在山脉子数组
     * @param args
     */
    public static void main(String[] args) {
        LongestMountain longestMountain = new LongestMountain();
        int[] arr = new int[]{2,1,4,7,3,2,5};
        System.out.println(longestMountain.longestMountain(arr));
    }

    /**
     * 枚举山顶
     * 获取从左到右，从右到左走到最高的山顶点，路径相加 并加上山顶值 即可
     * @param arr
     * @return int
     */
    public int longestMountain(int[] arr) {
        int ans = 0;
        int len = arr.length;
        if (len == 0) {
            return 0;
        }
        int[] left = new int[len];
        for (int i = 1; i < len; i++) {
            left[i] = arr[i - 1] < arr[i] ? left[i - 1] + 1 : 0;
        }
        int[] right = new int[len];
        for (int i = len - 2; i >= 0; i--) {
            right[i] = arr[i + 1] < arr[i] ? right[i + 1] + 1 : 0;
        }
        for (int i = 0; i < len; i++) {
            if (left[i] > 0 && right[i] > 0) {
                ans = Math.max(right[i] + left[i] + 1, ans);
            }
        }
        return ans;
    }
}
